// https://leetcode.cn/problems/decode-ways

// 题干：一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
//'A' -> "1"'B' -> "2"...'Z' -> "26"
//要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。
// 例如，"11106" 可以映射为："AAJF" ，将消息分组为 (1 1 10 6)"KJF" ，将消息分组为 (11 10 6)
//注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
//给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
//题目数据保证答案肯定是一个 32 位 的整数。

// 示例：输入：s = "12"
//      输出：2

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int numDecodings(string s) {
        // 1.状态表示
        // dp[i]表示以i为结尾的时候，解码方法的总数

        // 2.根据最近的一步来分析问题（状态转移方程）
        // 我们发现，dp[i]可以单独解码，或者可能与前一位合体解码
        // 单独解码有可能成功，要求字符串在1~9，此时dp[i-1];失败的话，此时为0
        // 合体解码，成功的话 要求10*s[i-1]+a位于[10,26]区间，因为不能有前导0！ 成功的话dp[i-2];失败的话0

        int n = s.size();
        vector<int> dp(n);

        dp[0] = s[0] != '0';
        if (n == 1) return dp[0];

        if (s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + (s[1] - '0'); // 前两个位置所表示的数
        if (t >= 10 && t <= 26) dp[1] += 1;

        for (int i = 2 ; i < n ; i++) {
            if (s[i] != '0') dp[i] += dp[i - 1]; // 单独编码
            int t = (s[i - 1] - '0') * 10 + s[i] - '0'; // 第二种情况所对应的数
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }

        return dp.back();
    }
};

int main()
{
    Solution sol;
    string s = "12";

    cout << sol.numDecodings(s) << endl;
    
    return 0;
}




